package cxydmmszl.chapter04.t066;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * <li style="color: red;">Prob</li>
 * 最长公共子串问题
 * <li style="color: green;">Desc</li>
 * 给定两个字符串 str1 和 str2，输出两个字符串的最长公共子串，如果最长公共子串为空，输出 -1。
 * <li style="color: green;">Input</li>
 * 输入包括两行，第一行代表字符串srr1，第二行代表字符串str2。
 * (1≤length(str1),length(str2)≤5000)
 * <li style="color: green;">Output</li>
 * 输出包括一行，代表最长公共子串。
 * <li style="color: blue;">Link</li> CD33
 *
 * @author habitplus
 * @since 2021-10-08 21:34
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str1 = br.readLine();
        String str2 = br.readLine();
        br.close();

        String s = lcs2(str1, str2);
        System.out.println(s);
    }

    private static String lcs1(String str1, String str2) {
        if (str1 == null || str2 == null || str1.length() == 0 || str2.length() == 0) {
            return "-1";
        }

        char[] chs1 = str1.toCharArray();
        char[] chs2 = str2.toCharArray();
        int len1 = chs1.length;
        int len2 = chs2.length;
        // dp[i][j] 表示在 str1[0,i] 和 str2[0,j]上，且分别以 str1[i] 和 str2[j] 结尾的最长的公共子串的长度
        int[][] dp = new int[len1][len2];

        // 第一行
        for (int j = 0; j < len2; j++) {
            dp[0][j] = chs1[0] == chs2[j] ? 1 : 0;
        }
        // 第一列
        for (int i = 0; i < len1; i++) {
            dp[i][0] = chs1[i] == chs2[0] ? 1 : 0;
        }

        for (int i = 1; i < len1; i++) {
            for (int j = 1; j < len2; j++) {
                dp[i][j] = chs1[i] == chs2[j] ? dp[i-1][j-1] + 1 : 0;
            }
        }

        // 求最长的子串
        int maxLen = 0;
        int k = 0;
        for (int i = 0; i < len1; i++) {
            for (int j = 0; j < len2; j++) {
                if (maxLen < dp[i][j]) {
                    maxLen = dp[i][j];
                    k = i;
                }
            }
        }

        return maxLen == 0 ? "-1" : str1.substring(k - maxLen + 1, k + 1);
    }

    private static String lcs2(String str1, String str2) {
        if (str1 == null || str2 == null || str1.length() == 0 || str2.length() == 0) {
            return "-1";
        }

        char[] chs1 = str1.toCharArray();
        char[] chs2 = str2.toCharArray();
        int len1 = chs1.length;
        int len2 = chs2.length;
        int row = 0;
        int col = len2 - 1;
        int maxLen = 0;
        int k = 0;
        int i, j, len;
        while (row < len1) {
            i = row;
            j = col;
            len = 0;
            while (i < len1 && j < len2) {
                if (chs1[i] == chs2[j]) {
                    len++;
                } else {
                    len = 0;
                }

                if (maxLen < len) {
                    maxLen = len;
                    k = i;
                }
                i++;
                j++;
            }

            if (col > 0) {
                col--;
            } else {
                row++;
            }
        }

        return maxLen == 0 ? "-1" : str1.substring(k - maxLen + 1, k + 1);
    }
}
